"""
Problem 30: https://projecteuler.net/problem=30

Problem Statement (Digit Fifth Power )

Surprisingly there are only three numbers that can be written as the sum of fourth
powers of their digits:

1634 = 1^4 + 6^4 + 3^4 + 4^4
8208 = 8^4 + 2^4 + 0^4 + 8^4
9474 = 9^4 + 4^4 + 7^4 + 4^4
As 1 = 1^4 is not a sum it is not included.

The sum of these numbers is 1634 + 8208 + 9474 = 19316.

Find the sum of all the numbers that can be written as the sum of fifth powers of their
digits.

(9^5)=59,049‬
59049*7=4,13,343 (which is only 6 digit number )
So, number greater than 9,99,999 are rejected
and also 59049*3=1,77,147 (which exceeds the criteria of number being 3 digit)
So, n>999
and hence a bound between (1000,1000000)
"""

# _*_ conding:UTF-8 _*_
'''
@author = Kuperain
@email = kuperain@aliyun.com
@IDE = VSCODE Python3.8.3
@creat_time = 2022/5/11
'''




from tkinter.font import nametofont
def solution(p: int = 5) -> int:
    '''
    (d(n-1), d(n-2), ...,d2,d1,d0) = d(n-1)^p + d(n-2)^p +...+ d0^p
    10^(n-1) < n * 9^p
    10^(n-1) / n < 9^p, 
    where 
        # (10^x)/x is an increasing function, and 9^p is a constant

    >>> print(solution(4))
    19316
    '''

    if p < 2:
        raise ValueError('p >=2')

    n = 2
    while 10**(n-1) < n * (9**p):
        n += 1

    np = {i: i**p for i in range(10)}
    # {0: 0, 1: 1, 2: 32, 3: 243, 4: 1024, 5: 3125,
    #  6: 7776, 7: 16807, 8: 32768, 9: 59049}

    total = 0
    for k in range(10, 10**n):
        sums = sum(list(map(lambda x: np[x], map(int, list(str(k))))))
        if k == sums:
            # print(k)
            total += k

    return total


if __name__ == "__main__":
    import doctest
    doctest.testmod(verbose=False)

    print(solution())
    # 443839
    print('OK!')
